'Weak Dependency Graph [60.0]'
------------------------------
Answer: YES(?,O(n^1))
Input Problem: innermost runtime-complexity with respect to
Rules:
{ f(a()) -> f(c(a()))
, f(c(X)) -> X
, f(c(a())) -> f(d(b()))
, f(a()) -> f(d(a()))
, f(d(X)) -> X
, f(c(b())) -> f(d(a()))
, e(g(X)) -> e(X)}
Details:
We have computed the following set of weak (innermost) dependency pairs:
{ f^#(a()) -> c_0(f^#(c(a())))
, f^#(c(X)) -> c_1()
, f^#(c(a())) -> c_2(f^#(d(b())))
, f^#(a()) -> c_3(f^#(d(a())))
, f^#(d(X)) -> c_4()
, f^#(c(b())) -> c_5(f^#(d(a())))
, e^#(g(X)) -> c_6(e^#(X))}
The usable rules are:
{}
The estimated dependency graph contains the following edges:
{f^#(a()) -> c_0(f^#(c(a())))}
==> {f^#(c(a())) -> c_2(f^#(d(b())))}
{f^#(a()) -> c_0(f^#(c(a())))}
==> {f^#(c(X)) -> c_1()}
{f^#(c(a())) -> c_2(f^#(d(b())))}
==> {f^#(d(X)) -> c_4()}
{f^#(a()) -> c_3(f^#(d(a())))}
==> {f^#(d(X)) -> c_4()}
{f^#(c(b())) -> c_5(f^#(d(a())))}
==> {f^#(d(X)) -> c_4()}
{e^#(g(X)) -> c_6(e^#(X))}
==> {e^#(g(X)) -> c_6(e^#(X))}
We consider the following path(s):
1) { f^#(a()) -> c_0(f^#(c(a())))
, f^#(c(a())) -> c_2(f^#(d(b())))
, f^#(d(X)) -> c_4()}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
f(x1) = [0] x1 + [0]
a() = [0]
c(x1) = [0] x1 + [0]
d(x1) = [0] x1 + [0]
b() = [0]
e(x1) = [0] x1 + [0]
g(x1) = [0] x1 + [0]
f^#(x1) = [0] x1 + [0]
c_0(x1) = [0] x1 + [0]
c_1() = [0]
c_2(x1) = [0] x1 + [0]
c_3(x1) = [0] x1 + [0]
c_4() = [0]
c_5(x1) = [0] x1 + [0]
e^#(x1) = [0] x1 + [0]
c_6(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {f^#(d(X)) -> c_4()}
Weak Rules:
{ f^#(c(a())) -> c_2(f^#(d(b())))
, f^#(a()) -> c_0(f^#(c(a())))}
Details:
We apply the weight gap principle, strictly orienting the rules
{f^#(d(X)) -> c_4()}
and weakly orienting the rules
{ f^#(c(a())) -> c_2(f^#(d(b())))
, f^#(a()) -> c_0(f^#(c(a())))}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{f^#(d(X)) -> c_4()}
Details:
Interpretation Functions:
f(x1) = [0] x1 + [0]
a() = [0]
c(x1) = [1] x1 + [0]
d(x1) = [1] x1 + [0]
b() = [0]
e(x1) = [0] x1 + [0]
g(x1) = [0] x1 + [0]
f^#(x1) = [1] x1 + [1]
c_0(x1) = [1] x1 + [0]
c_1() = [0]
c_2(x1) = [1] x1 + [0]
c_3(x1) = [0] x1 + [0]
c_4() = [0]
c_5(x1) = [0] x1 + [0]
e^#(x1) = [0] x1 + [0]
c_6(x1) = [0] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules:
{ f^#(d(X)) -> c_4()
, f^#(c(a())) -> c_2(f^#(d(b())))
, f^#(a()) -> c_0(f^#(c(a())))}
Details:
The given problem does not contain any strict rules
2) { f^#(a()) -> c_0(f^#(c(a())))
, f^#(c(a())) -> c_2(f^#(d(b())))}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
f(x1) = [0] x1 + [0]
a() = [0]
c(x1) = [0] x1 + [0]
d(x1) = [0] x1 + [0]
b() = [0]
e(x1) = [0] x1 + [0]
g(x1) = [0] x1 + [0]
f^#(x1) = [0] x1 + [0]
c_0(x1) = [0] x1 + [0]
c_1() = [0]
c_2(x1) = [0] x1 + [0]
c_3(x1) = [0] x1 + [0]
c_4() = [0]
c_5(x1) = [0] x1 + [0]
e^#(x1) = [0] x1 + [0]
c_6(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {f^#(c(a())) -> c_2(f^#(d(b())))}
Weak Rules: {f^#(a()) -> c_0(f^#(c(a())))}
Details:
We apply the weight gap principle, strictly orienting the rules
{f^#(c(a())) -> c_2(f^#(d(b())))}
and weakly orienting the rules
{f^#(a()) -> c_0(f^#(c(a())))}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{f^#(c(a())) -> c_2(f^#(d(b())))}
Details:
Interpretation Functions:
f(x1) = [0] x1 + [0]
a() = [8]
c(x1) = [1] x1 + [0]
d(x1) = [1] x1 + [0]
b() = [4]
e(x1) = [0] x1 + [0]
g(x1) = [0] x1 + [0]
f^#(x1) = [1] x1 + [12]
c_0(x1) = [1] x1 + [0]
c_1() = [0]
c_2(x1) = [1] x1 + [1]
c_3(x1) = [0] x1 + [0]
c_4() = [0]
c_5(x1) = [0] x1 + [0]
e^#(x1) = [0] x1 + [0]
c_6(x1) = [0] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules:
{ f^#(c(a())) -> c_2(f^#(d(b())))
, f^#(a()) -> c_0(f^#(c(a())))}
Details:
The given problem does not contain any strict rules
3) { f^#(a()) -> c_3(f^#(d(a())))
, f^#(d(X)) -> c_4()}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
f(x1) = [0] x1 + [0]
a() = [0]
c(x1) = [0] x1 + [0]
d(x1) = [0] x1 + [0]
b() = [0]
e(x1) = [0] x1 + [0]
g(x1) = [0] x1 + [0]
f^#(x1) = [0] x1 + [0]
c_0(x1) = [0] x1 + [0]
c_1() = [0]
c_2(x1) = [0] x1 + [0]
c_3(x1) = [0] x1 + [0]
c_4() = [0]
c_5(x1) = [0] x1 + [0]
e^#(x1) = [0] x1 + [0]
c_6(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {f^#(d(X)) -> c_4()}
Weak Rules: {f^#(a()) -> c_3(f^#(d(a())))}
Details:
We apply the weight gap principle, strictly orienting the rules
{f^#(d(X)) -> c_4()}
and weakly orienting the rules
{f^#(a()) -> c_3(f^#(d(a())))}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{f^#(d(X)) -> c_4()}
Details:
Interpretation Functions:
f(x1) = [0] x1 + [0]
a() = [0]
c(x1) = [0] x1 + [0]
d(x1) = [1] x1 + [0]
b() = [0]
e(x1) = [0] x1 + [0]
g(x1) = [0] x1 + [0]
f^#(x1) = [1] x1 + [1]
c_0(x1) = [0] x1 + [0]
c_1() = [0]
c_2(x1) = [0] x1 + [0]
c_3(x1) = [1] x1 + [0]
c_4() = [0]
c_5(x1) = [0] x1 + [0]
e^#(x1) = [0] x1 + [0]
c_6(x1) = [0] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules:
{ f^#(d(X)) -> c_4()
, f^#(a()) -> c_3(f^#(d(a())))}
Details:
The given problem does not contain any strict rules
4) {f^#(c(b())) -> c_5(f^#(d(a())))}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
f(x1) = [0] x1 + [0]
a() = [0]
c(x1) = [0] x1 + [0]
d(x1) = [0] x1 + [0]
b() = [0]
e(x1) = [0] x1 + [0]
g(x1) = [0] x1 + [0]
f^#(x1) = [0] x1 + [0]
c_0(x1) = [0] x1 + [0]
c_1() = [0]
c_2(x1) = [0] x1 + [0]
c_3(x1) = [0] x1 + [0]
c_4() = [0]
c_5(x1) = [0] x1 + [0]
e^#(x1) = [0] x1 + [0]
c_6(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {f^#(c(b())) -> c_5(f^#(d(a())))}
Weak Rules: {}
Details:
We apply the weight gap principle, strictly orienting the rules
{f^#(c(b())) -> c_5(f^#(d(a())))}
and weakly orienting the rules
{}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{f^#(c(b())) -> c_5(f^#(d(a())))}
Details:
Interpretation Functions:
f(x1) = [0] x1 + [0]
a() = [4]
c(x1) = [1] x1 + [8]
d(x1) = [1] x1 + [0]
b() = [0]
e(x1) = [0] x1 + [0]
g(x1) = [0] x1 + [0]
f^#(x1) = [1] x1 + [12]
c_0(x1) = [0] x1 + [0]
c_1() = [0]
c_2(x1) = [0] x1 + [0]
c_3(x1) = [0] x1 + [0]
c_4() = [0]
c_5(x1) = [1] x1 + [0]
e^#(x1) = [0] x1 + [0]
c_6(x1) = [0] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules: {f^#(c(b())) -> c_5(f^#(d(a())))}
Details:
The given problem does not contain any strict rules
5) { f^#(c(b())) -> c_5(f^#(d(a())))
, f^#(d(X)) -> c_4()}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
f(x1) = [0] x1 + [0]
a() = [0]
c(x1) = [0] x1 + [0]
d(x1) = [0] x1 + [0]
b() = [0]
e(x1) = [0] x1 + [0]
g(x1) = [0] x1 + [0]
f^#(x1) = [0] x1 + [0]
c_0(x1) = [0] x1 + [0]
c_1() = [0]
c_2(x1) = [0] x1 + [0]
c_3(x1) = [0] x1 + [0]
c_4() = [0]
c_5(x1) = [0] x1 + [0]
e^#(x1) = [0] x1 + [0]
c_6(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {f^#(d(X)) -> c_4()}
Weak Rules: {f^#(c(b())) -> c_5(f^#(d(a())))}
Details:
We apply the weight gap principle, strictly orienting the rules
{f^#(d(X)) -> c_4()}
and weakly orienting the rules
{f^#(c(b())) -> c_5(f^#(d(a())))}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{f^#(d(X)) -> c_4()}
Details:
Interpretation Functions:
f(x1) = [0] x1 + [0]
a() = [0]
c(x1) = [1] x1 + [0]
d(x1) = [1] x1 + [0]
b() = [0]
e(x1) = [0] x1 + [0]
g(x1) = [0] x1 + [0]
f^#(x1) = [1] x1 + [1]
c_0(x1) = [0] x1 + [0]
c_1() = [0]
c_2(x1) = [0] x1 + [0]
c_3(x1) = [0] x1 + [0]
c_4() = [0]
c_5(x1) = [1] x1 + [0]
e^#(x1) = [0] x1 + [0]
c_6(x1) = [0] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules:
{ f^#(d(X)) -> c_4()
, f^#(c(b())) -> c_5(f^#(d(a())))}
Details:
The given problem does not contain any strict rules
6) { f^#(a()) -> c_0(f^#(c(a())))
, f^#(c(X)) -> c_1()}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
f(x1) = [0] x1 + [0]
a() = [0]
c(x1) = [0] x1 + [0]
d(x1) = [0] x1 + [0]
b() = [0]
e(x1) = [0] x1 + [0]
g(x1) = [0] x1 + [0]
f^#(x1) = [0] x1 + [0]
c_0(x1) = [0] x1 + [0]
c_1() = [0]
c_2(x1) = [0] x1 + [0]
c_3(x1) = [0] x1 + [0]
c_4() = [0]
c_5(x1) = [0] x1 + [0]
e^#(x1) = [0] x1 + [0]
c_6(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {f^#(c(X)) -> c_1()}
Weak Rules: {f^#(a()) -> c_0(f^#(c(a())))}
Details:
We apply the weight gap principle, strictly orienting the rules
{f^#(c(X)) -> c_1()}
and weakly orienting the rules
{f^#(a()) -> c_0(f^#(c(a())))}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{f^#(c(X)) -> c_1()}
Details:
Interpretation Functions:
f(x1) = [0] x1 + [0]
a() = [0]
c(x1) = [1] x1 + [0]
d(x1) = [0] x1 + [0]
b() = [0]
e(x1) = [0] x1 + [0]
g(x1) = [0] x1 + [0]
f^#(x1) = [1] x1 + [1]
c_0(x1) = [1] x1 + [0]
c_1() = [0]
c_2(x1) = [0] x1 + [0]
c_3(x1) = [0] x1 + [0]
c_4() = [0]
c_5(x1) = [0] x1 + [0]
e^#(x1) = [0] x1 + [0]
c_6(x1) = [0] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules:
{ f^#(c(X)) -> c_1()
, f^#(a()) -> c_0(f^#(c(a())))}
Details:
The given problem does not contain any strict rules
7) {e^#(g(X)) -> c_6(e^#(X))}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
f(x1) = [0] x1 + [0]
a() = [0]
c(x1) = [0] x1 + [0]
d(x1) = [0] x1 + [0]
b() = [0]
e(x1) = [0] x1 + [0]
g(x1) = [0] x1 + [0]
f^#(x1) = [0] x1 + [0]
c_0(x1) = [0] x1 + [0]
c_1() = [0]
c_2(x1) = [0] x1 + [0]
c_3(x1) = [0] x1 + [0]
c_4() = [0]
c_5(x1) = [0] x1 + [0]
e^#(x1) = [0] x1 + [0]
c_6(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {e^#(g(X)) -> c_6(e^#(X))}
Weak Rules: {}
Details:
We apply the weight gap principle, strictly orienting the rules
{e^#(g(X)) -> c_6(e^#(X))}
and weakly orienting the rules
{}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{e^#(g(X)) -> c_6(e^#(X))}
Details:
Interpretation Functions:
f(x1) = [0] x1 + [0]
a() = [0]
c(x1) = [0] x1 + [0]
d(x1) = [0] x1 + [0]
b() = [0]
e(x1) = [0] x1 + [0]
g(x1) = [1] x1 + [8]
f^#(x1) = [0] x1 + [0]
c_0(x1) = [0] x1 + [0]
c_1() = [0]
c_2(x1) = [0] x1 + [0]
c_3(x1) = [0] x1 + [0]
c_4() = [0]
c_5(x1) = [0] x1 + [0]
e^#(x1) = [1] x1 + [1]
c_6(x1) = [1] x1 + [3]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules: {e^#(g(X)) -> c_6(e^#(X))}
Details:
The given problem does not contain any strict rules
8) {f^#(a()) -> c_3(f^#(d(a())))}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
f(x1) = [0] x1 + [0]
a() = [0]
c(x1) = [0] x1 + [0]
d(x1) = [0] x1 + [0]
b() = [0]
e(x1) = [0] x1 + [0]
g(x1) = [0] x1 + [0]
f^#(x1) = [0] x1 + [0]
c_0(x1) = [0] x1 + [0]
c_1() = [0]
c_2(x1) = [0] x1 + [0]
c_3(x1) = [0] x1 + [0]
c_4() = [0]
c_5(x1) = [0] x1 + [0]
e^#(x1) = [0] x1 + [0]
c_6(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {f^#(a()) -> c_3(f^#(d(a())))}
Weak Rules: {}
Details:
'fastest of 'combine', 'Bounds with default enrichment', 'Bounds with default enrichment''
------------------------------------------------------------------------------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {f^#(a()) -> c_3(f^#(d(a())))}
Weak Rules: {}
Details:
The problem was solved by processor 'Bounds with default enrichment':
'Bounds with default enrichment'
--------------------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {f^#(a()) -> c_3(f^#(d(a())))}
Weak Rules: {}
Details:
The problem is Match-bounded by 1.
The enriched problem is compatible with the following automaton:
{ a_0() -> 2
, a_1() -> 11
, d_0(2) -> 4
, d_0(4) -> 4
, d_1(11) -> 10
, f^#_0(2) -> 8
, f^#_0(4) -> 8
, f^#_1(10) -> 9
, c_3_1(9) -> 8}
9) {f^#(a()) -> c_0(f^#(c(a())))}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
f(x1) = [0] x1 + [0]
a() = [0]
c(x1) = [0] x1 + [0]
d(x1) = [0] x1 + [0]
b() = [0]
e(x1) = [0] x1 + [0]
g(x1) = [0] x1 + [0]
f^#(x1) = [0] x1 + [0]
c_0(x1) = [0] x1 + [0]
c_1() = [0]
c_2(x1) = [0] x1 + [0]
c_3(x1) = [0] x1 + [0]
c_4() = [0]
c_5(x1) = [0] x1 + [0]
e^#(x1) = [0] x1 + [0]
c_6(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {f^#(a()) -> c_0(f^#(c(a())))}
Weak Rules: {}
Details:
'fastest of 'combine', 'Bounds with default enrichment', 'Bounds with default enrichment''
------------------------------------------------------------------------------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {f^#(a()) -> c_0(f^#(c(a())))}
Weak Rules: {}
Details:
The problem was solved by processor 'Bounds with default enrichment':
'Bounds with default enrichment'
--------------------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {f^#(a()) -> c_0(f^#(c(a())))}
Weak Rules: {}
Details:
The problem is Match-bounded by 1.
The enriched problem is compatible with the following automaton:
{ a_0() -> 2
, a_1() -> 11
, c_0(2) -> 3
, c_0(3) -> 3
, c_1(11) -> 10
, f^#_0(2) -> 8
, f^#_0(3) -> 8
, f^#_1(10) -> 9
, c_0_1(9) -> 8}